<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>План лекций</title>
  <link href=styles/styles.css rel="stylesheet" type="text/css">
</head>
<h2>Темы для сборов в Казахстане (март 2013)</h2>
<ol>
  <li>Разрезы и потоки</li>
  <ol>
    <li>Потоки.Основы</li>
    <ol>
      <li>Определение потока, разреза, декомпозиции</li>
      <li>Теорема и алгоритм Форда-Фалкерсона за O(|f|*E)</li>
      <li>Алгоритм декомпозиции за O(VE), восстановления разреза за O(E)</li>
      <li>Проталкивание максимума по пути. Эдмондс-Карп за O(EV<sup>2</sup>). Масштабирование потока за O(E<sup>2</sup> log)</li>
      <li>Вершинный поток, несколько стоков и истоков.</li>
      <li>Задачи на Потоки.</li>
    </ol></li>
    <li>Потоки.MinCost</li>
    <ol>
      <li>Алгоритм Диница, скрещивание с масштабированием</li>
      <li>MinCost поток, поиск потока размера 0, переход Форд-Беллманом</li>
      <li>Дейкстра и потенциалы</li>
      <li>Задачи на потоки и mincost потоки</li>
      <li>Поток с избытаками и недостатками.</li>
      <li>[L,R] поток MinCost-м</li>
      <li>[L,R] поток за O(Flow)</li>
    </ol></li>
    <li>Потоки.Hard</li>
    <ol>
      <li>Проталкивание предпотока (определения, базовый алгоритм)</li>
      <li>Алгоритм за O(V<sup>3</sup>): while (1) { перебираем все вершины }</li>
      <li>Оценка времени работы: O(VE) + количество просмотров></li>
      <li>High Level optimization, просмотр только вершин с избытком</li>
      <li>Global relabeling, быстрый алгоритм</li>
      <li>Задачи на разрез (инструменты и скидки, максимально насыщенный подграф и т.д.)</li>
      <li>Поиск mincost потока через цикл минимального среднего веса (а также минимальная по весу циркуляция)</li>
    </ol></li>
  </ol></li>
  <li>Алгоритмы на строках</li>
  <ol>
    <li>Level1 (хранение, set&lt;string&gt;, sort, Z-функция, префикс-функция, период строки, минимальный циклический сдвиг)</li>
    <li>Level2 (хэши, суфф.массив за nlog<sup>2</sup>n, бор, сжатый бор, суф.дерево за n<sup>2</sup>, пара примеров задач, все lcp за n<sup>2</sup>, lcp соседних за nlogn)</li>
    <li>Level3 (суф.массив за nlogn, lcp соседних за линию, суф.дерево за линию, построение массива по дереву и дерева по массиву, много примеров задач)</li>
    <li>Level4 (суф.автомат: определение, построение за линию, использование для решения задач; построение суф.дерева по автомату и автомата по дереву)</li>
    <li>BonusLevel (корневой эффект, какие хэши можно сломать, а какие нет, восстановление строки по z и префикс функциям, поиск тандемного повтора)</li>
  </ol></li>
  <li>Геометрия</li>
  <ol>
    <li>2D base (Пересечение окружностей, общая касательная к окружностям. Вычисление площади. Выпуклая оболочка. Расстояние между отрезками, от круга до отрезка. Вычисление углов, биссектриса угла.)</li>
    <li>2D advanced (Пересечение выпуклых и невыпуклых многоугольников, полуплоскостей. Пересечение и объединение кругов. Планарный граф, разрезание на грани. Сортировка по углу. Метод двух указателей: прямая, разделяющая многоугольники, общие касательные к многоугольникам; две самые дальние точки в 2D)</li>
    <li>3D base (Пересечение прямых. Расстояние между прямыми, отрезками. Расстояние от точки до плоскости. Вычисление объема многогранника.)</li>
    <li>3D advanced (Вычисление углов. Выпуклая оболочка. Ортоганализация Грамма-Шмидта. Объем d-мерной фигуры. Расстояние до d-мерной гиперплоскости.)</li>
    <li>Погрешность вещественных чисел (Откуда берется. Какова она в стандартных задачах. Нормализация.)</li>
  </ol></li>
  <li>Тактика выступления на контестах</li>
  <ol>
    <li>Читаем все условия. Каждую задачу успеваем обсудить 5 минут в первой половине контеста.</li>
    <li>Не тратим на задачу много времени. Если задача тормозит весь процесс, ее можно выкинуть.</li>
    <li>Компьютерное время -- не самоцель. Если решение не доделано, не пишем его.</li>
    <li>Используем монитор: есть сложные задачи, есть простые, есть задачи с потенциальными багами и без, есть баяны.</li>
    <li>Используем тестирующий сервер: можно специально заслать тупое решение и получить TL/WA.</li>
    <li>Цель стресс-теста и прочих фишек: уменьшить дисперсию результатов, сделать так, чтобы в худшем случае все было не так плохо.</li>
    <li>Эффект последних 100 минут контеста: остались сложные задачи, мозг устал. Полезно писать вдвоем. Полезно насильно отрываться от насущного и оценивать ситуацию в целом.</li>
    <li>Правильно ставим цель на тренировочном контесте и основной части соревнования: бороться нужно с задачами, а не с командами</li>
    <li>Правильно ставим цель на финальной части соревнования: покрыть "задачу минимум" с большой вероятностью лучше, чем "задачу максимум" с малой вероятностью</li>
    <li>Психология в команде. Помогайте друг другу, предлагайте помощь.</li>
    <li>Точка выбора. На выбор стоит потратить время. Лишние 3-5 минут. Не спешить.</li>
    <li>Сам себе капитан. Если каждый человек в команде понимает, что происходит, что будет и согласен с выбором, это хорошо.</li>
  </ol></li>
  <li>Технически сложные задачи</li>
  <ol>
    <li>Разбор выражений (арифметические: за O(N) со стеком и без стека, более сложные грамматики)</li>
    <li>Распарсить (программу, многочлен, строки, базу данных)</li>
    <li>Задачи на моделирование с большим количеством случаев (принцесса в лабиринте, люди в черном, ...)</li>
    <li>Разбор случаев (google-codejam-2012-finals-C: восстановление клетчатой плоскости, ...)</li>
  </ol></li>
  <li>Структуры данных</li>
  <ol>
    <li>Level1 (двусвязный список; стек, очередь и дэк на массиве; куча; частичные суммы 1d и 2d; Sparse Table; LCA двоичными подъемами; дерево отрезков без групповых операций)</li>
    <li>Level2 (LCA в Offline; LCA через RMQ; дерево отрезков с групповыми операциями; декартово дерево по явному и неявному ключу; scanline; куча примеров задач на данные темы)</li>
    <li>Level3 (дерево отрезков сортированных массивов, set-ов, декартовых деревьев; fractional cascading; КД-дерево; RMQ в Offline за O(1), RMQ в Online за O(1))</li>
    <li>Level4 (Персистентные деревья и массивы; Heavy-Light decomposition; Link-Cut; Splay-Tree; пополняемые структуры данных; функции на путях дерева в online и offline)</li>
    <li>BonusLevel (Необычные деревья: China-tree, перебаллансировка при size=2<sup>k</sup>; Garbage Collection; Стратегии выделения памяти)</li>
  </ol></li>
  <li>Динамическое программирование</li>
  <ol>
    <li>Level1 (Числа Фибоначчи, Каталана, Цэшки; Линейные динамика; Квадратные динамики; Задача о рюкзаке; Восстановление ответа; Динамика вперед, назад, ленивая; Представление динамики в виде графа)</li>
    <li>Level2 (Динамика на подотрезках; Динамика по дереву; Динамика по подмножествам; Внесение функции в параметры; Измельчение перехода; Лексмин ответ)</li>
    <li>Level3 (Meet-in-the-middle для динамики по подмножествам; Динамика по профилю, по скошенному профилю; Кодирование профиля; Использование двух указателей при пересчете; Более мощные два указателя)</li>
    <li>BonusLevel (Разбор классических сложных задач; Динамика на круге, разрезание круга; динамики с фишкой n = k * (n/k); линейная память при восстановлении ответа; метод 4-х русских)</li>
  </ol></li>
  <li>Алгоритмы на графах</li>
  <ol>
    <li>Level1 (Хранение графа, добавление ребер в граф, удаление ребер из графа; dfs, bfs; компоненты связности, раскраска в два цвета, поиск цикла, топологическая сортировка, динамика на ацикличном графе)</li>
    <li>Level2 (Краскал; Форд-Беллман; Флойд; Дейкстра с кучей; Прима; мосты, точки сочленения компоненты двусвязности)</li>
    <li>Level3 (2-SAT; Цикл минимального среднего веса, отрицательный цикл; 0-1-k bfs; k..2k bfs; Цикл минимальной длины; Эйлеров цикл; Гамильтонов путь и цикл)</li>
    <li>Level4 (Дополнение графа до сильносвязного; Борувка; Цикл минимального среднего веса за VE; dynamic connectivity)</li>
    <li>BonusLevel1 (Планарные графы: планарные графы, Эйлер, Эйлер для двудольных, Куратовский, Демукрон; Факты: Харари, укладка на гриде, 4 раскрашиваемость; док-во 5-раскрашиваемости)</li>
    <li>BonusLevel2 (Алгоритм Йена: модификация алгоритма поиска минимума в алгоритм поиска k-го минимума; Лексмин путь в ацикличном графе, лексмин кратчайший путь)</li>
  </ol></li>
  <li>Паросочетания и покраски</li>
  <ol>
    <li>Level1 (Кун, независимое и контролирующее множество; Стандартные графы: грид, строки и столбцы матрицы; Задачи на паросочетание в двудольном графе)</li>
    <li>Level2 (Алгоритм Хопкрофта-Карпа; рандомизированный алгоритм для произвольного граф; алгоритм Эдмондса; покрытие ацикличного графа путями)</li>
    <li>Level3 (Покраски вершин и ребер графа: теорема Буркса, Визинга, лемма Холла; алгоритмы покраски ребер k-регулярного и произвольного двудольного графа; максимальная антицепь, теорема Дилворта)</li>
  </ol></li>
  <li>Гаусс, Simplex</li>
  <ol>
    <li>Level1 (Гаусс: для невырожденной матрицы за O(n<sup>3</sup>); Вычисления по модулю p, случай кольца (+,-,*); Гаусс для произвольной матрицы, инкрементальный; Выделение базиса пространства; Гаусс для разреженной матрицы)</li>
    <li>Level2 (Задача линейного программирования; преобразования разных форм задачи друг в друга; базисный план; решение за C(n,m)*Gauss; поиск начального решения и состояние симплекса; переход в симплексе; случай для потока в неориентированных графах)</li>
  </ol></li>
  <li>Неточные задачи</li>
  <ol>
    <li>Методы оптимизации (локальные оптимизации; оптимальное дерево ветвления; генетический алгоритм; отжиг; перцептрон, он же нейрон)</li>
    <li>Задачи кластеризации и классификации (формулировка задачи кластеризации, классификации; алгоритмы кластеризация: k-means, fuzzy-clustering, метод опорных векторов; линейный классификатор; разбиение графа на подклики)</li>
  </ol></li>
  <li>Рандомизированные алгоритмы</li>
  <ol>
    <li>Level1 (2D-линпрог за O(n); покрытие точек кругом за O(n); декартово дерево; qsort; k-я статистика)</li>
    <li>Level2 (локализация точки в 2D; триангулция за O(nlogn); 3D-выпуклая оболочка за O(nlogn); Каргер-Штейнер за O(n<sup>2</sup>log<sup>2</sup>))</li>
  </ol></li>
  <li>Разная Математика</li>
  <ol>
    <li>Умножение матриц (Правильные for-ы; Правильное взятие по модулю; Штрассен; битовое-сжатие; метод четырех-русских)</li>
    <li>Длинная арифметика (Фурье; Оптимальное написание Фурье; Деление за nlogn через Фурье и метод Ньютона; Квадратный корень за nlogn)</li>
    <li>Читы: Быстрые проверки (A*B = C, det A = 0, expr1 = expr2)</li>
    <li>Численные методы: Поиск (корни многочленов: вещественные, комплексные; собственные числа и вектора)</li>
    <li>Численные методы: Метод итераций (решение систем линейных уравнений; решение задач про теорвер; нормализация матриц)</li>
    <li>Численные методы: Бинарный поиск. Троичный поиск. Их обобщения и ускорения. Более крутые методы (если функция соедржит много локальных минимумов).</li>
  </ol></li>
  <li>Теория чисел</li>
  <ol>
    <li>Level1 (Распределение простых чисел; Диофантовы уравнения; Быстрое возведение в степень; Решето Эратосфена с sqrt(n) памяти; Тест Ферма; Обратное по модулю; Вычисление Phi, d, D и других мультипликативных функций)</li>
    <li>Level2 (Формула включения-исключения; Тест Миллера-Рабина; Квадратные корни по модулю: алгоритм Шенкса и алгоритм с многочленами; Первообрзаный корень; Дискретное логарифмирование)</li>
    <li>Level3 (ro-эвристика; Поиск числа с максимальным количеством делителей; Количество простых чисел; Квадратичное решето: разложение на простые за полилогарифм)</li>
  </ol></li>
  <li>Техники оптимизации перебора</li>
  <ol>
    <li>Level1 (Меморизация (запоминание), отсечение по ответу, iterative deepening; Представление в виде ацикличного графа; задача поиска пути, минимального по весу пути; Примеры задач)</li>
    <li>Level2 (Алгоритм A*, применение Дейкстры в переборе; AB-отсечение, оценка снизу sqrt(n); dfs/bfs/fb; совмещение запоминания и отсечения по ответу; random-shuffle, несколько запусков; k-first; храним поколение лучших; meet-in-the-middle; метод четырех-русских; Примеры задач)</li>
  </ol></li>
  <li>Жадные алгоритмы.</li>
  <ol>
    <li>Level1 (Разбор простых задач на сортировку; Разбор стандартных задач из теории расписаний)</li>
    <li>Level2 (Сложные задачи из теории расписаний; Матроиды: графовый, линейный, трансверсальный)</li>
    <li>Level3 (Пересечение матроидов; объединение матроидов; примеры задач)</li>
  </ol></li>
  <li>Игры на графах</li>
  <ol>
    <li>Level1 (Случай ацикличного графа;; Ретроанализ, Подсчет длины игры; Гранди; Примеры: Hacking Bush, Штирлиц, 3D-карлсон)</li>
    <li>Level2 (Смит; игра про покраску ребер двудольного графа; Стратегии для игры "Крестики-Нолики" и других неточных игр)</li>
  </ol></li>
  <li>Комбинаторика</li>
  <ol>
    <li>Level1 (Количество скобочных последовательностей, сочетаний, перестановок; лексикографически k-й; объект по номеру, номер по объекту; следующий; количество объектов от L до R)</li>
    <li>Level2 (Разбор конкрентых задач вида "сумма всех чисел от L до R, состоящих только из цифр 1 и 2; L, R <= 10<sup>100</sup>")</li>
  </ol></li>
</ol>
